package leetcode.simple._previous;

//小青蛙跳台阶问题，动态规划
public class NumWays {

    public static void main(String[] args) {
        NumWays ways = new NumWays();
        System.out.println(ways.numWays_(7));

    }

    public int numWays(int n) {
        if (n == 0 || n == 1) return 1;
        int[] arr = new int[n + 1];
        arr[0] = 1;
        arr[1] = 1;

        for (int i = 3; i < n + 1; i++) {
            arr[i] = (arr[i - 1] % 1000000007 + arr[i - 2] % 1000000007) % 1000000007;
        }

        return arr[n];
    }

    public int numWays_(int n) {
        if (n == 1 || n == 0) return 1;

        return method(n);

    }

    private int method(int n) {
        if (n == 1 || n == 2) return n;

        return (numWays_(n - 2) % 1000000007 + numWays_(n - 1) % 1000000007) % 1000000007;
    }
}
